package cn.bellychang.leetcode.question088;

/**
 * @author ChangLiang
 * @date 2021/2/19
 */
public class Solution3 {

    public void merge(int[] nums1, int m, int[] nums2, int n) {

        int index2 = 0;
        for (int i = m; i < m + n; i++) {
            nums1[i] = nums2[index2];
            index2++;
        }
        // insertion sort
        for (int i = m; i < m + n; i++) {

            int curr = i;
            while (true) {
                if (curr == 0) {
                    break;
                }
                int prev = curr - 1;
                if (nums1[curr] < nums1[prev]) {
                    swap(nums1, prev, curr);
                    curr--;
                } else {
                    break;
                }
            }
        }
    }

    private void swap(int[] nums1, int i, int j) {
        int temp = nums1[i];
        nums1[i] = nums1[j];
        nums1[j] = temp;
    }

}
